The technology relates to a technique of searching for a path by A-Star algorithm. In particular, the technology relates to a technique especially useful in searching for an optimal path even when a surrounding situation of a movable body involves a change.
A-Star algorithm has been widely used as a method of searching for various paths such as a flight path of an aircraft.
A-Star algorithm is a searching algorithm that sequentially performs searching, from a start node, for a node that minimizes a value of cost f*(n) expressed by the following expression, and thereby determines an optimal path.f*(n)=g*(n)+h*(n)
where g*(n) is an estimated smallest cost value of a path from the start node to a node “n” on which the searching is being currently performed, and h*(n) is an estimated smallest cost value of a path from the node “n” to a goal node.
It is possible, with the foregoing algorithm, to update the estimated smallest cost value g*(n) during the searching and thereby make the estimated smallest cost value g*(n) closer to an actual smallest cost value g(n). It is to be noted that the term “estimated” value used herein refers to a provisional value related to a node on which the searching is being currently performed.
In contrast, the estimated smallest cost value h*(n) is an estimated value in a literal sense. Upon using A-Star algorithm, an optimal solution is guaranteed when the estimated smallest cost value h*(n) is smaller than an actual smallest cost value h(n) of the path from the node “n” to the goal node.
Hence, the optimal solution is not guaranteed when the condition h*(n)<h(n) that the estimated smallest cost value h*(n) is smaller than the actual smallest cost value h(n) is not satisfied, for example, attributed to a change in the surrounding situation of the movable body due to a factor such as a change in location of a goal during the searching.
To address the foregoing issue, Howie Choset. “Robotic Motion Planning: A* and D* Search” [online]. Robotics Institute. retrieved on Jan. 7, 2016 from the Internet: <URL: http://www.cs.cmu.edu/18motionplanning/lecture/AppH-astar-dstar_howie.pdf> discloses a technique in which, when a new hindrance becomes present during the searching, the smallest cost value h(n) of a path from a node on which the searching has been already performed to the goal node is updated with a new value, and the optimal path from the node on which the searching is being currently performed to the goal node is thereby determined efficiently.